Football League

Memory limit: 32 MB

There are teams in a football league (we assume that is even). During a season each team plays with every other team exactly once. The season consists of turns. Every team plays exactly once during a turn. It is desired for a team to play consecutive matches on different stadia: one at home stadium, and one away, etc. Unfortunately it is not always possible to construct such a game schedule that no team plays twice in a row at home stadium, or twice in a row away. When constructing the schedule the number of such situations should be minimized. (For example, if a team plays once away, then four times at home stadium and then once away, it counts as three such situations.)

Your task is to minimize the number of situations in which a team plays twice in a row at home or away and to construct such game schedule for the whole season. The schedule should consist of turns. Each turn consists of matches - each team plays exactly one match. There are matches in the whole season, and every two teams should play exactly one match against each other. Each match is played at one of the opponents' stadium - one team plays at home stadium and the other one plays away. The total number of situations in which a team plays two consecutive matches at home or away should be minimal.

Task

Write a program, that:

• reads the number of teams from the standard input,
• computes the minimum total number of situations in which a team plays twice in a row at home or away and constructs the game schedule,
• writes the result to standard output.

Input

The first and only one line of the standard input contains one even integer () - the number of teams.

Output

The first line of the standard output should contain a single integer - the minimum total number of situations in which a team plays twice in a row at home or away. The following lines should contain a game schedule: the line should contain the description of the -th turn.

The description of a turn consists of different numbers from separated by single spaces. For the pair denotes a match between teams and . Team plays at home and team plays away.

Example

For the input data:

4

the correct result is:

2
1 4 2 3
1 2 4 3
2 4 3 1

Task author: Jakub Pawlewicz.